public class code5 {
    //得保证最后的健康值为负的最大
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;

        int[][] dp = new int[m+1][n+1];//dp[i][j]：从这个位置到终点所需的最低健康点数

        //初始化：拓展的位置全部初始化为正无穷，只有dp[m][n-1]和dp[m-1][n]为1
        for(int i=0;i<=n-1;i++) dp[m][i]=Integer.MAX_VALUE;
        for(int i=0;i<=m-1;i++) dp[i][n]=Integer.MAX_VALUE;
        dp[m][n-1] = dp[m-1][n] = 1;

        for(int i=m-1;i>=0;i--)
        {
            for(int j=n-1;j>=0;j--)
            {
                dp[i][j] = Math.min(dp[i][j+1],dp[i+1][j])-dungeon[i][j];
                dp[i][j] = Math.max(1,dp[i][j]);
            }

        }
        return dp[0][0];
    }
}
